package MyString;

import java.util.Arrays;

public class KMP {
    // kmp的前戏 next数组的建立
    public static int[] next(IString p) throws Exception{
        int[] next = new int[p.length()];
        // 定义前后缀指针
        // 前缀指针
        int j = 0;
        // 后缀指针
        int i = 1;
        // 定义数组首元素
        next[0] = 0;
        for(; i<p.length(); i++){
            // 处理第一个情况 当 下标 i 和 j 不相等时
            while(j>0 && p.charAt(i)!=p.charAt(j)){
                // j 是最长相等的前后缀长度 而该next数组里面的前一位代表的就是 最长相等的前后缀长度
                // j需要等于 j-1 下标的next数组元素
                // 继续匹配，直到
                j = next[j-1];
            }
            // 处理第二个情况相等时
            if(p.charAt(i) == p.charAt(j)){
                // j 指针 像后进一位
                j = j+1;
                next[i] = j;
            }else if(j == 0){
                // 第一种情况没法跳出循环到这一步
                next[i] = j;
            }
        }
        return next;
    }
    // kmp 算法使用next数组解答
    public static int kmp(IString strValue, IString contrastValue) throws Exception {
        // strValue 总字符串
        // contrastValue待匹配字符串

        // 返回的值是 匹配字符串的首下标索引。
        if(contrastValue.length() > 0 && contrastValue.length()<=strValue.length()){
            int[] next = next(contrastValue);
            // kmp 匹配算法前面就和普通的算法一样 2个指针一起移动比较
            // strValue 指针
            int i = 0;
            // contrastValue 指针
            int j = 0;
            for(; i<strValue.length();){
                // 匹配如果相等前进
                // 这里的if的顺序一定要理清楚不然数组下标越界随时发生
                if(strValue.charAt(i) == contrastValue.charAt(j)){
                    // 这里要么是双方匹配成功
                    //  只有匹配成功了才往前前进双方才一起前进
                    i++;
                    j++;
                }else if(j==0 && strValue.charAt(i) != contrastValue.charAt(j)){
                    // 最坏的情况就是contrastValue指针到底
                    // 但是 此时还没有能够匹配上
                    // 结束这个无意义的比较 strValue指针直接往前走
                    i++;
                }else if(strValue.charAt(i) != contrastValue.charAt(j)){
                    // 取最长相等的前后缀长度 而该next数组的前一位就是 这个长度
                    // 得到长度后重新开始比较
                    j = next[j-1];
                }
            }
            if(j== contrastValue.length()) {
                // 返回下标
                return i - j;
            }else{
                return -1;
            }
        }else {
            return -1;
        }
    }


    public static void main(String[] args) throws Exception {
        IString strValue = new SqString("aabaabaaf");
        IString contrastValue = new SqString("aabaag");

        int value = kmp(strValue, contrastValue);
        System.out.println(value);
    }


}
